//索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S[i] = {A[i], A[A[i]], A[A[A[i
//]]], ... }且遵守以下的规则。 
//
// 假设选择索引为i的元素A[i]为S的第一个元素，S的下一个元素应该是A[A[i]]，之后是A[A[A[i]]]... 以此类推，不断添加直到S出现重复的元
//素。 
//
// 
//
// 示例 1: 
//
// 输入: A = [5,4,0,3,1,6,2]
//输出: 4
//解释: 
//A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
//
//其中一种最长的 S[K]:
//S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
// 
//
// 
//
// 提示： 
//
// 
// N是[1, 20,000]之间的整数。 
// A中不含有重复的元素。 
// A中的元素大小在[0, N-1]之间。 
// 
// Related Topics 深度优先搜索 数组 
// 👍 181 👎 0

package com.cute.leetcode.editor.cn;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class ArrayNesting {
    public static void main(String[] args) {
        Solution solution = new ArrayNesting().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 比较直接的思路，提交时超时了：
     *      借助一个set保存已经存过的下标，每次存放前先进行判断
     *      如果已经存在，则将当前set的值与max进行比较，然后将set清空，在将i置为nus[pre]的下一个位置
     *      如果不存在就添加到set中去，然后将pre值设置为nums[pre]，即为下一个元素的下标
     *      官方的第一个题解也是暴力搜索，肯定会超时
     *      public int arrayNesting(int[] nums) {
     *         int res = 0;
     *         for (int i = 0; i < nums.length; i++) {
     *             int start = nums[i], count = 0;
     *             do {
     *                 start = nums[start];
     *                 count++;
     *             }
     *             while (start != nums[i]);
     *             res = Math.max(res, count);
     *
     *         }
     *         return res;
     *     }
     *
     *
     *
     * 题解：是在暴力求解的方法上进行了优化，原理如下：
     *      假如存在四个数 5 0 6 2 存在了循环，那么这四个数的位置无论哪个是起始点都回形成相同的访问循环
     *      所以对访问过的位置进行标记，没有访问过再进行遍历就行了
     *      而且nums中元素各不相同，所以i!=j时绝对不会访问到相同的元素，可以直接在原数组中进行访问标记，这样会节省空间
     */
    public int arrayNesting(int[] nums) {
        /* int max = Integer.MIN_VALUE;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length;) {
            int pre = i;
            while (pre < nums.length){
                if (set.contains(nums[pre])){
                    max = Math.max(max, set.size());
                    i = pre+1;
                    set.clear();
                    break;
                }else {
                    set.add(nums[pre]);
                    pre = nums[pre];
                }
            }
        }
        return Math.max(max, set.size());*/
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length ; i++) {
            if (nums[i]!=-1){
                int count = 0;//这里必须从0开始，因为这种遍历方式会最后再访问开始节点一次
                int start = nums[i];
                while (nums[start]!=-1){
                    //如果循环是5620-->5620，0应该是最先访问到的同时也会再结束前再次访问到
                    //所以上边的count从0开始，不然会出错
                    int temp = start;
                    start = nums[start];
                    count++;
                    nums[temp] = -1;
                }
                res = Math.max(res, count);
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}